The present invention relates to uses made of field programmable gate arrays (FPGAs), in particular to use of an FPGA to route information from selected input points to selected output points.
FPGAs are frequently used for telecommunication. An essential aspect of telecommunication is the ability to route information from any source to any desired destination. A crossbar switch accomplishes this purpose.
FIG. 1 shows a simple crossbar switch. Eight input lines IN0 through IN7 carry input signals and eight output lines OUT0 through OUT7 provide output signals. An array of connectors can be selectively turned on to provide any of the input signals as an output signal. For example, turning on connector C0,0 connects input line IN0 to output line OUT0. Turning on connector C0,7 connects input line IN0 to output line OUT7. It is important that an output line not be driven by more than one input signal so that no contention occurs, and for this reason, crossbar switches are often implemented as multiplexers.
FIG. 2 shows a multiplexer implementation of the crossbar switch of FIG. 1, in which multiplexer control signals select one and only one of the input signals to provide as an output signal. For example, multiplexer control signals A0 select which of the eight input signals IN0 through IN7 will be provided as output signal OUT0.
As the number of input and output signals increases, the size of the crossbar switch becomes larger in proportion to the product of the number of input and output signals. For example, an array accommodating 1000 input signals and 1000 output signals would require a million connectors. If implemented with multiplexers, the crossbar switch would require 1000 multiplexers, each with 1000 input signals. U.S. Pat. No. 6,288,568 to Bauer and Young entitled xe2x80x9cFPGA Architecture With Deep Look-Up Table RAMsxe2x80x9d describes an FPGA architecture having lookup tables that can generate a function of eight input signals.
FIG. 3 is a copy of FIG. 20 of the Bauer and Young patent and represents one configurable logic block (CLB) of to an FPGA. One possible function that can be generated by this flexible structure is a multiplexer. In FIG. 3, the lookup tables are 4-input lookup tables (LUTs), and thus each LUT can implement a 2-input multiplexer. The inputs applied on three of the lines F1, F2, F3, and F4 or G1, G2, G3, and G4 to each 4-input LUT are two multiplexer data inputs and one multiplexer control input. Eight lookup tables are present in the CLB of FIG. 3, each labeled LUT-F or LUT-G.
To form a conventional crossbar switch, the LUTs are each configured to implement a 2-input multiplexer with these three inputs. Sixteen data signals can be applied to these eight LUTs, two to each LUT. The lowest order multiplexer control bit C0 is applied to all eight LUTs and serves as the control bit for each of the eight 2:1 multiplexers. The next lowest order control bit C1 is applied to each of four multiplexers labeled F5, which receive outputs from pairs of the LUTs. Thus the outputs of the F5 multiplexers are 4:1 multiplexer outputs. Pairs of the F5 multiplexers feed F6 multiplexers as controlled by control bit C2, and pairs of the F6 multiplexers feed the F7 multiplexer as controlled by control bit C3. The F7 multiplexer thus provides the output of a 16:1 multiplexer. Another structure the same as FIG. 3 but receiving 16 different input signals receives the same control signals C0 through C3. The F8 multiplexer receives input signals from two F7 multiplexers and is controlled by a still higher order control bit C4 to produce a 32:1 multiplexer output signal. Thus an adjacent pair of CLBs can implement a 32:1 multiplexer.
Of course, providing these data and control signals requires routing through the FPGA. This routing has not been shown because it is easy to understand that the necessary route for each signal is formed by programmably connecting together the interconnect lines to get the data and control input signals from their origins and to get the output signals to their destinations.
Still wider multiplexer functions are formed by using another level of hierarchy. For example, a 1024:1 multiplexer can be formed in a very large FPGA by configuring 32 additional pairs of CLBs to each implement a 32:1 multiplexer, then finally forming a higher level structure, also from two CLBs, in which the input signals are the F8 output signals from the 32 pairs of CLBs. Thus the output of this final structure is the output of a 1024:1 multiplexer, and has consumed 64+2 CLBs or 66 CLBs. A square crossbar switch (1024 inputs and 1024 outputs) would require 1024 of these structures or a total of 67,584 CLBs.
One of the largest FPGA available from Xilinx Inc. today has on the order of 8,000 CLBs, so such a switch can not be implemented this way in such an FPGA but would require about 9 FPGAs.
It would be desirable to implement a large crossbar switch in an FPGA in a manner that is denser than this prior art implementation, preferably one that will fit into a single FPGA.
According to the invention, a switch such as a crossbar switch is implemented in an FPGA by using the FPGA""s configuration memory cells to control multiplexers that perform the routing of signals through the switch. Thus, the multiplexer control is established during configuration or reconfiguration of the FPGA and the multiplexer input data passes through the configuration multiplexers. This contrasts with the above described prior art implementation babe both the multiplexer input signals and the multiplexer control signals are applied to inputs pins of the FPGA after it has been configured. In one embodiment, the invention is implemented in an FPGA in which each CLB of the FPGA has several LUTs, for example eight 4-input LUTs, and an input multiplexer (IMUX) routes signals to each LUT. The IMUX receives control signals from the configuration memory cells. Rather than changing the switch configuration by changing control input signals, the switch configuration is changed by reconfiguring one or several IMUXs of the FPGA.
As an optional feature of the invention, an input signal applied to a single pin is deserialized and applied to several different internal input lines. In one embodiment, each input signal on one input pin is applied to four different input lines. Likewise, four output signals are serialized and placed onto a single output pin. For an FPGA with a given number of pins, this increases the amount of logic the FPGA can process. An FPGA having on the order of 250 input pins and 250 output pins (or 500 I/O pins) can implement a 1000xc3x971000 crossbar switch by making use of a 4:1 serializer/deserializer (SERDES) feature. If each input and output signal is applied to two pins as a low voltage differential signal (LVDS), and a 4:1 SERDES is used, 1000 physical pins are required for a 1000xc3x971000 crossbar switch.
Of course, consideration must be made for how the user changes or partly changes the configuration in order to reconfigure the IMUXs. Changing control signals in the IMUX is slower than simply applying a new multiplexer control signal to a LUT, as described above for a prior art crossbar switch implementation. However, in some applications this is acceptable because data needs to flow at high speed, but its destination changes only occasionally. Some FPGAs are reconfigured by shifting data into a configuration frame register in the FPGA and loading the frame register data into the designated frame. It may be necessary to load a full frame of data during a partial reconfiguration. In Virtex-II FPGAs available from Xilinx, Inc., this is true. An IMUX can be reconfigured by loading four frames of data. Typically, the user will want to disconnect one input terminal from an output terminal and connect another input terminal to the output terminal. This operation requires loading no more than six frames of configuration data and takes about 140 microseconds. This reconfiguration rate is fast enough for some communications applications. Importantly, the connectivity of the crossbar switch can be changed with a small amount of reconfiguration.
A benefit of the invention is that it is an order of magnitude more dense than the prior art method. For example, in a Virtex-II FPGA, a single CLB can implement eight 144:1 multiplexers, one in each LUT and associated IMUX. Making use of all these inputs may be impractical due to limitations in routing available in the Virtex-II FPGA. In one embodiment, eight 33:1 multiplexers are implemented in one CLB. That compares to the prior art method in which two CLBs can implement one 32:1 multiplexer. This is more than a 16:1 improvement in density. Of course other embodiments will differ in the details of the FPGA architecture, and thus in the relative improvement.
In communications use, FPGAS implementing crossbar switches are reconfigured to change which input is connected to which output, but most of the configuration is retained. In one embodiment, to change the connectivity, the lookup tables and routing are not reconfigured, and only the IMUXs are reconfigured. A table of configuration values may be stored in a computer that configures the FPGA, one set of bits to be turned on for each input-to-output connection, and used to set up the configuration bitstream for a partial reconfiguration due to changing connectivity of the crossbar switch. An algorithm for generating the bits may also be used. By taking advantage of the regularity and the fact that the CLBs are identical, the algorithm would simply generate bitstream instructions based on the desired location with a CLB.
In yet another optional feature of the invention, a pipelining structure can be included in the FPGA such that input signals routed on long horizontal or vertical paths are captured and retransmitted periodically. If it is necessary that all signal paths experience the same latency, shift registers can be implemented to delay signals on fast paths so that all signal paths experience the same latency.
It is typically desired to implement a crossbar switch as a static structure, but to change the connectivity every time there is a change in the use of the switch. It is desirable to make a change in connectivity without disruption of any other connections that the switch is currently providing. A Virtex-II FPGA can be partially reconfigured by changing a few frames of configuration data. Ongoing communication can continue on all paths except the ones being reconfigured. Those IMUXs that stay the same in the reconfigured column are unaffected and can continue to pass data.